---
title: "Java 模板"
created: 2025-12-20
---
# Java 模板

```java
import java.util.*;
import java.io.*;

public class Template {
    
    // ==================== 基础定义 ====================
    static final int INF = 0x3f3f3f3f;
    static final long LINF = 0x3f3f3f3f3f3f3f3fL;
    static final int MOD = (int)1e9 + 7;
    
    static int[] dx4 = {-1, 0, 1, 0};
    static int[] dy4 = {0, 1, 0, -1};
    static int[] dx8 = {-1,-1,0,1,1,1,0,-1};
    static int[] dy8 = {0,1,1,1,0,-1,-1,-1};
    
    // ==================== 快读快写 ====================
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static StringTokenizer st;
    
    static String next() throws IOException {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }
    static int nextInt() throws IOException { return Integer.parseInt(next()); }
    static long nextLong() throws IOException { return Long.parseLong(next()); }
    
    // ==================== 30级：DFS三种枚举 ====================
    
    // 1. 指数型枚举（子集）
    static void dfsSubset(int u, int n, int[] nums, int[] st, List<List<Integer>> result) {
        if (u == n) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++)
                if (st[i] == 1) subset.add(nums[i]);
            result.add(subset);
            return;
        }
        st[u] = 0; // 不选
        dfsSubset(u + 1, n, nums, st, result);
        st[u] = 1; // 选
        dfsSubset(u + 1, n, nums, st, result);
        st[u] = 0;
    }
    
    // 2. 全排列枚举
    static void dfsPermutation(int[] nums, int idx, List<List<Integer>> result) {
        if (idx == nums.length) {
            List<Integer> perm = new ArrayList<>();
            for (int x : nums) perm.add(x);
            result.add(perm);
            return;
        }
        for (int i = idx; i < nums.length; i++) {
            swap(nums, i, idx);
            dfsPermutation(nums, idx + 1, result);
            swap(nums, i, idx);
        }
    }
    static void swap(int[] arr, int i, int j) {
        int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
    }
    
    // 3. 组合型枚举 C(n,m)
    static void dfsCombination(int u, int start, int[] nums, int m, 
                               List<Integer> path, List<List<Integer>> result) {
        if (path.size() + (nums.length - start) < m) return; // 剪枝
        if (path.size() == m) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            dfsCombination(u + 1, i + 1, nums, m, path, result);
            path.remove(path.size() - 1);
        }
    }
    
    // ==================== BFS模板 ====================
    static int[][] bfs(int[][] grid, int sx, int sy) {
        int n = grid.length, m = grid[0].length;
        int[][] dist = new int[n][m];
        for (int[] row : dist) Arrays.fill(row, -1);
        
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{sx, sy});
        dist[sx][sy] = 0;
        
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0], y = cur[1];
            
            for (int i = 0; i < 4; i++) {
                int nx = x + dx4[i], ny = y + dy4[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m 
                    && dist[nx][ny] == -1 && grid[nx][ny] == 0) {
                    dist[nx][ny] = dist[x][y] + 1;
                    q.offer(new int[]{nx, ny});
                }
            }
        }
        return dist;
    }
    
    // ==================== 洪水填充（连通块计数） ====================
    static int floodFill(char[][] grid) {
        int n = grid.length, m = grid[0].length;
        boolean[][] vis = new boolean[n][m];
        int cnt = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '#' && !vis[i][j]) {
                    dfsFlood(grid, vis, i, j);
                    cnt++;
                }
            }
        }
        return cnt;
    }
    
    static void dfsFlood(char[][] g, boolean[][] vis, int x, int y) {
        vis[x][y] = true;
        for (int i = 0; i < 8; i++) {
            int nx = x + dx8[i], ny = y + dy8[i];
            if (nx >= 0 && nx < g.length && ny >= 0 && ny < g[0].length
                && !vis[nx][ny] && g[nx][ny] == '#') {
                dfsFlood(g, vis, nx, ny);
            }
        }
    }
    
    // ==================== 八皇后 ====================
    static List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        boolean[] col = new boolean[n];
        boolean[] dg = new boolean[2 * n];  // 主对角线 x+y
        boolean[] udg = new boolean[2 * n]; // 副对角线 n-x+y
        
        dfsQueens(0, n, board, col, dg, udg, res);
        return res;
    }
    
    static void dfsQueens(int u, int n, char[][] board, 
                          boolean[] col, boolean[] dg, boolean[] udg,
                          List<List<String>> res) {
        if (u == n) {
            List<String> solution = new ArrayList<>();
            for (char[] row : board) solution.add(new String(row));
            res.add(solution);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
                board[u][i] = 'Q';
                col[i] = dg[u + i] = udg[n - u + i] = true;
                dfsQueens(u + 1, n, board, col, dg, udg, res);
                col[i] = dg[u + i] = udg[n - u + i] = false;
                board[u][i] = '.';
            }
        }
    }
    
    // ==================== 100级：背包问题 ====================
    
    // 01背包
    static int knapsack01(int[] v, int[] w, int m) {
        int[] f = new int[m + 1];
        for (int i = 0; i < v.length; i++)
            for (int j = m; j >= v[i]; j--)
                f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
        return f[m];
    }
    
    // 完全背包
    static int knapsackComplete(int[] v, int[] w, int m) {
        int[] f = new int[m + 1];
        for (int i = 0; i < v.length; i++)
            for (int j = v[i]; j <= m; j++)
                f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
        return f[m];
    }
    
    // ==================== LIS ====================
    
    // O(n²) 朴素
    static int lisBasic(int[] a) {
        int n = a.length;
        int[] f = new int[n];
        int res = 0;
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++)
                if (a[j] < a[i]) f[i] = Math.max(f[i], f[j] + 1);
            res = Math.max(res, f[i]);
        }
        return res;
    }
    
    // O(nlogn) 贪心+二分
    static int lisBinary(int[] a) {
        int[] q = new int[a.length];
        int len = 0;
        for (int x : a) {
            int l = 0, r = len;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (q[mid] >= x) r = mid;
                else l = mid + 1;
            }
            q[r] = x;
            if (r == len) len++;
        }
        return len;
    }
    
    // ==================== 1000级：二分 ====================
    
    // 第一个 >= target 的位置 (lower_bound)
    static int lowerBound(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return r;
    }
    
    // 最后一个 <= target 的位置 (upper_bound - 1)
    static int upperBound(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        return r;
    }
    
    // ==================== 1e6级：并查集 ====================
    static class DSU {
        int[] parent, rank;
        
        DSU(int n) {
            parent = new int[n + 1];
            rank = new int[n + 1];
            for (int i = 0; i <= n; i++) parent[i] = i;
        }
        
        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }
        
        void unite(int x, int y) {
            int fx = find(x), fy = find(y);
            if (fx == fy) return;
            if (rank[fx] < rank[fy]) { int t = fx; fx = fy; fy = t; }
            parent[fy] = fx;
            if (rank[fx] == rank[fy]) rank[fx]++;
        }
        
        boolean connected(int x, int y) {
            return find(x) == find(y);
        }
    }
    
    // ==================== 字符串哈希 ====================
    static class StringHash {
        static final long P = 131;
        long[] h, p;
        
        StringHash(String s) {
            int n = s.length();
            h = new long[n + 1];
            p = new long[n + 1];
            p[0] = 1;
            for (int i = 1; i <= n; i++) {
                h[i] = h[i - 1] * P + s.charAt(i - 1);
                p[i] = p[i - 1] * P;
            }
        }
        
        long getHash(int l, int r) { // 1-indexed
            return h[r] - h[l - 1] * p[r - l + 1];
        }
    }
    
    // ==================== 1e7级：线性筛 ====================
    static int[] getPrimes(int n) {
        boolean[] st = new boolean[n + 1];
        int[] primes = new int[n + 1];
        int cnt = 0;
        for (int i = 2; i <= n; i++) {
            if (!st[i]) primes[cnt++] = i;
            for (int j = 0; primes[j] <= n / i; j++) {
                st[primes[j] * i] = true;
                if (i % primes[j] == 0) break;
            }
        }
        return Arrays.copyOf(primes, cnt);
    }
    
    // ==================== 1e9级：判断质数 & 约数 ====================
    static boolean isPrime(long n) {
        if (n < 2) return false;
        for (long i = 2; i * i <= n; i++)
            if (n % i == 0) return false;
        return true;
    }
    
    static List<Long> getDivisors(long n) {
        List<Long> res = new ArrayList<>();
        for (long i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                res.add(i);
                if (i != n / i) res.add(n / i);
            }
        }
        Collections.sort(res);
        return res;
    }
    
    // ==================== 1e18级：GCD & 快速幂 ====================
    static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }
    
    static long qmi(long a, long k, long p) {
        long res = 1 % p;
        while (k > 0) {
            if ((k & 1) == 1) res = res * a % p;
            k >>= 1;
            a = a * a % p;
        }
        return res;
    }
    
    // ==================== 高精度 ====================
    static class BigNum {
        // Java直接用 BigInteger 即可
        // import java.math.BigInteger;
        // BigInteger a = new BigInteger("12345678901234567890");
        // a.add(b), a.subtract(b), a.multiply(b), a.divide(b)
        // a.mod(b), a.gcd(b), a.pow(n)
    }
    
    // ==================== 日期问题 ====================
    static int[] days = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    
    static boolean isLeap(int y) {
        return (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0);
    }
    
    static int getDays(int y, int m) {
        return days[m] + (m == 2 && isLeap(y) ? 1 : 0);
    }
    
    static int[] nextDay(int y, int m, int d) {
        d++;
        if (d > getDays(y, m)) { d = 1; m++; }
        if (m > 12) { m = 1; y++; }
        return new int[]{y, m, d};
    }
    
    // ==================== 主函数模板 ====================
    public static void main(String[] args) throws IOException {
        int n = nextInt();
        // ... 
        out.flush();
    }
}


```